The present invention relates generally to rasterizers and, more particularly, to accelerating the conversion of primitives defined by vertexes to equivalent images composed of pixel patterns that can be stored and manipulated as sets of bits.
Raster displays are commonly used in computer graphics systems. These displays store graphics images as a matrix of the smallest picture elements that can be displayed on a screen (xe2x80x9cpixelsxe2x80x9d) with data representing each pixel being stored in a display buffer. This data specifies the display attributes for each pixel on the screen such as the intensity and color of the pixel. An entire image is read from the display buffer and displayed on the screen by sequentially scanning out horizontal rows of pixel data or xe2x80x9cscan lines.xe2x80x9d
Raster display systems commonly use polygons as basic building blocks or xe2x80x9cprimitivesxe2x80x9d for drawing more complex images. Triangles are a common basic primitive for polygon drawing systems, since a triangle is the simplest polygon and more complex polygons can always be represented as sets of triangles. The process of drawing triangles and other geometric primitives on the screen is known as xe2x80x9crasterization.xe2x80x9d
An important part of rasterization involves determining which pixels fall within a given triangle. Rasterization systems generally step from pixel to pixel in various ways and determine whether or not to xe2x80x9crender,xe2x80x9d i.e. draw into a frame buffer or pixel map, each pixel as part of the triangle. This, in turn, determines how to set the data in the display buffer representing each pixel. Various traversal algorithms have been developed for moving from pixel to pixel in a way such that all pixels within the triangle are covered.
Rasterization systems sometimes represent a triangle as a set of three edge-functions. An edge function is a line equation representing a straight line, which serves to subdivide a two-dimensional plane. Edge functions classify each point within the plane as falling into one of three regions: the region xe2x80x9cinsidexe2x80x9d of the triangle, the region xe2x80x9coutsidexe2x80x9d of the triangle or the region representing a line itself. The type of edge function that will be discussed has the property that points xe2x80x9cinsidexe2x80x9d of the triangle have a value greater than zero, points xe2x80x9coutsidexe2x80x9d have a value less than zero, and points exactly on the line have a value of zero. This is shown in Prior Art FIG. 1. Applied to rasterization systems, the two-dimensional plane is represented by the graphics screen, points are represented by individual pixels, and the edge function serves to subdivide the graphics screen.
The union of three edges, or more particularly three half-planes, each of which is specified by edge functions, create triangles. It is possible to define more complex polygons by using Boolean combinations of more than three edges. Since the rasterization of triangles involves determining which pixels to render, a tiebreaker rule is generally applied to pixels that lie exactly on any of the edges to determine whether the pixels are to be considered interior or exterior to the triangle.
As shown in Prior Art FIG. 1A, each pixel has associated with it a set of edge variables, (e0, e1 and e2), which are proportional to the signed distance between the pixel and the three respective edges. The value of each edge variable is determined for a given triangle by evaluating the three edge functions, f0 (x,y), f1 (x,y) and f2 (x,y) for the pixel location. It is important to note that it can be determined whether or not a pixel falls within a triangle by looking at only the signs of e0, e1 and e2.
In determining which pixels to render within a triangle, typical rasterization systems compute the values of the edge variables, (e0, e1 and e2), for a given set of three edge functions and a given pixel position, and then use a set of increment values (xcex94eoutside, xcex94einside, etc.) to determine the edge variable values for adjacent pixels. The rasterization system traverses the triangle, adding the increment values to the current values as a traversal algorithm steps from pixel to pixel.
With reference again to Prior Art FIG. 1, a line is illustrated that is defined by two points: (X,Y) and (X+dX, Y+dY). As noted above, this line can be used to divide the two dimensional space into three regions: all points xe2x80x9coutsidexe2x80x9d of, xe2x80x9cinsidexe2x80x9d of, and exactly on the line.
The edge f(x,y) can be defined as:
f(x,y)=(xxe2x88x92X)dYxe2x88x92(yxe2x88x92Y)dX.
This function has the useful property that its value is related to the position of the point (x,y) relative to the edge defined by the points (X,Y) and (X+dX, Y+dY):
f(x,y) greater than 0 if (x,y) is xe2x80x9cinsidexe2x80x9d;
f(x,y)=0 if (x,y) is exactly on the line;
and
f(x,y) less than 0 if (x,y) is xe2x80x9coutsidexe2x80x9d.
Existing rasterization systems commonly use this function, since it can be computed incrementally by simple addition:
f(x+1,y)=f(x,y)+dY;
and
f(x,y+1)=f(x,y)xe2x88x92dX.
A variety of different traversal algorithms are presently used by different rasterization systems in the rendering process. Any algorithm guaranteed to cover all of the pixels within the triangle can be used. For example, some solutions involve following the sides of the triangle while identifying a horizontal or vertical span of pixels therein. Following the sides of the triangle is adequate for the triangle edges, but if the triangle is clipped by a near or far plane, these boundaries are not known explicitly and cannot be followed as easily as the triangle edges.
Other methods search in a recursively narrowing manner. Recursion, however, can require an excessive amount of processing. This is due to the fact that many more points might be tested than there are inside the triangle.
Still other methods test individual pixels one at a time. Individual pixel testing works well, but generates only one pixel at a time. This is inadequate for devices that process multiple pixels simultaneously.
There is therefore a need for a rasterization system that overcomes the problems and deficiencies associated with the prior art methods.
A method, apparatus and article of manufacture are provided for performing area rasterization using sense points. Upon receipt of a primitive, i.e. a triangle, line equation coefficients of line equations are determined for lines that define the primitive. Thereafter, a plurality of points is positioned on or near the primitive. Such points define an enclosed convex region and reside at corners of the convex region. Next, the line equations are evaluated at the points. During operation, the points and convex region are moved based on the evaluation of the line equations for the purpose of identifying an area in the primitive for rendering pixels therein.
In one embodiment, the points may be initially positioned to enclose a vertex of the primitive. The evaluation includes determining if the points reside in the primitive. Such determination as to whether the points reside in the primitive may include determining whether the evaluation of the line equations renders a positive value or a negative value. For example, the evaluation of a line equation at a point that renders a negative value indicates that such point resides outside the primitive.
In another embodiment, the points may be moved along a first row until lateral edges of the primitive are identified after which the points are moved along a second row below the first row. Further, a starting position of the points on subsequent rows may reside adjacent a position on a previous row where the points were at least partially in the primitive. The points may then be moved from the starting position in a first direction until a first lateral edge of the primitive is identified after which the points are moved from the starting position in a second direction to identify a second lateral edge of the primitive.
One aspect of the present invention thus includes outputting multiple pixels at a time in the primitive that is described by line equations. Using the line equations avoids solving for the clipped intersections, such as the near and far Z planes with the primitive edges. Since solving for such intersections involves division, it is costly and can slow hardware performance.
The present invention thus moves or steps the convex region defined by the points around inside the primitive, using the points as a guide. Since the convex region defined by the points may be large, many pixels may be tested simultaneously. During use, if all the points are inside all edges of the primitive, then all the enclosed pixels are drawable. A significant advantage is thus afforded by testing the corners of the convex region defined by the points, namely the ability of proving an arbitrary area of the primitive is completely inside, completely outside or split. Only in the latter case do the individual pixels in the convex region defined by the points need to be further tested to ascertain which pixels are inside or outside the primitive.
These and other advantages of the present invention will become apparent upon reading the following detailed description and studying the various figures of the drawings.